import os
from queue import Queue, LifoQueue, PriorityQueue
from threading import Thread

import pygame

from Games.MazeDTO import randint, generate_maze


class GameMaze:
    def __init__(self, minsize=25, maxsize=50):
        # 游戏的一些属性
        self.WIDTH = 600
        self.HEADER = 30
        self.HEIGHT = 660
        self.WINDOW = (self.WIDTH, self.HEIGHT)
        self.TITLE = "迷宫"
        self.FPS = 60
        self.FONT_SIZE = 16
        # self.FONT = pygame.font.SysFont('华文宋体', self.FONT_SIZE)
        self.BUTTONS = []
        self.white = (255, 255, 255)
        self.black = (0, 0, 0)
        self.red = (255, 0, 0)
        self.green = (0, 255, 0)
        self.cyan = (0, 255, 255)
        # 迷宫大小
        self.min = minsize
        self.max = maxsize

    def start_game(self):
        pygame.init()
        self.SCREEN = pygame.display.set_mode(self.WINDOW)
        pygame.display.set_caption(self.TITLE)

        path = os.path.join(os.path.abspath(os.path.dirname(__file__)), 'FZSTK.TTF')
        self.FONT = pygame.font.Font(path, self.FONT_SIZE)

    def draw_rect(self, x, y, len, color):
        pygame.draw.rect(self.SCREEN, color, [x, y, len, len], 0)

    def draw_button(self, x, y, color, len, height, text):
        pygame.draw.rect(self.SCREEN, color, [x, y, len, height], 1)
        text_surface = self.FONT.render(text, True, color)
        self.SCREEN.blit(text_surface, (x + 20, y + 2))

    def move(self, maze, cur_pos, end_cell, dir):
        loc = cur_pos.loc
        next_x = loc[1] + dir[1]
        next_y = loc[0] + dir[0]
        if self.can_move(maze, next_x, next_y, end_cell):
            maze[next_y][next_x].pre = cur_pos
            if maze[next_y][next_x].type == 2:
                cur_pos.type = 3
            else:
                cur_pos.type = 2
            cur_pos = maze[next_y][next_x]
        return cur_pos

    def ai_move(self, maze, cur_pos, end_cell, dir, render=True):
        loc = cur_pos.loc
        next_x = loc[1] + dir[1]
        next_y = loc[0] + dir[0]
        if self.can_move(maze, next_x, next_y, end_cell):
            maze[next_y][next_x].pre = cur_pos
            if maze[next_y][next_x].type == 2:
                cur_pos.type = 3
            else:
                cur_pos.type = 2
            cur_pos = maze[next_y][next_x]
            if render:
                self.draw_maze(maze, cur_pos)
        return cur_pos

    def db_astar(self, maze, start_cell, end_cell, q, p, alist):
        f_q = PriorityQueue()
        l_q = PriorityQueue()
        start_cell.isvisited = True
        end_cell.isvisitedl = True
        priority = 0
        f_q.put((0, start_cell.loc))
        l_q.put((0, end_cell.loc))
        curf = start_cell
        curl = end_cell
        dirs = [[-1, 0], [1, 0], [0, 1], [0, -1]]
        flag = True
        e_loc = end_cell.loc
        s_loc = start_cell.loc
        while f_q.qsize() > 0 and l_q.qsize() > 0 and flag:
            locf = f_q.get()[1]
            locl = l_q.get()[1]
            curf = maze[locf[0]][locf[1]]
            curl = maze[locl[0]][locl[1]]
            if not (curf.isvisitedl or curl.isvisited):
                q.put(curf)
                q.put(curl)
                for dir in dirs:
                    next_xf = locf[1] + dir[1]
                    next_yf = locf[0] + dir[0]
                    disf_to_s = curf.step
                    disf_to_e = abs(next_yf - e_loc[0]) + abs(next_xf - e_loc[1])
                    scoref = disf_to_s * priority + disf_to_e
                    if self.can_move(maze, next_xf, next_yf, end_cell):
                        nextf = maze[next_yf][next_xf]
                        if nextf.isvisitedl:
                            curl = nextf
                            flag = False
                            break
                        if not nextf.isvisited:
                            nextf.pre = curf
                            nextf.isvisited = True
                            nextf.step = curf.step + 1
                            f_q.put((scoref, nextf.loc))
                    next_xl = locl[1] + dir[1]
                    next_yl = locl[0] + dir[0]
                    disl_to_s = curf.step
                    disl_to_e = abs(next_yl - s_loc[0]) + abs(next_xl - s_loc[1])
                    scorel = disl_to_s * priority + disl_to_e
                    if self.can_move(maze, next_xl, next_yl, start_cell):
                        nextl = maze[next_yl][next_xl]
                        if nextl.isvisited:
                            curf = nextl
                            flag = False
                            break
                        if not nextl.isvisitedl:
                            nextl.pre = curl
                            nextl.isvisitedl = True
                            nextl.step = curl.step + 1
                            l_q.put((scorel, nextl.loc))
        if p.qsize() == 0:
            self.split_quene(q.qsize(), p)
        while curf.pre is not None:
            alist.append(curf)
            curf = curf.pre
        alist.append(curf)
        alist.reverse()
        while curl.pre is not None:
            alist.append(curl)
            curl = curl.pre
        alist.append(curl)
        print("DONE")
        return alist

    def a_star(self, maze, start_cell, end_cell, q, p, alist):
        f_q = PriorityQueue()
        priority = 0
        # maxscore = len(maze) * len(maze[0]) * (1 + priority)
        f_q.put((1, start_cell.loc))
        # s_loc = start_cell.loc
        e_loc = end_cell.loc
        dirs = [[-1, 0], [1, 0], [0, 1], [0, -1]]
        while f_q.qsize() > 0 and end_cell.pre is None:
            loc = f_q.get()[1]
            cur = maze[loc[0]][loc[1]]
            q.put(cur)
            for dir in dirs:
                next_x = loc[1] + dir[1]
                next_y = loc[0] + dir[0]
                dis_to_s = cur.step
                dis_to_e = abs(next_y - e_loc[0]) + abs(next_x - e_loc[1])
                score = dis_to_s * priority + dis_to_e
                if self.can_move(maze, next_x, next_y, end_cell):
                    next = maze[next_y][next_x]
                    if next.isvisited:
                        continue
                    next.pre = cur
                    next.step = cur.step + 1
                    next.isvisited = True
                    f_q.put((score, next.loc))
        if p.qsize() == 0:
            self.split_quene(q.qsize(), p)
        while end_cell.pre is not None:
            alist.append(end_cell)
            end_cell = end_cell.pre
        alist.append(end_cell)
        alist.reverse()
        return alist

    def dfs_move(self, maze, start_cell, end_cell, q, p, alist):
        f_q = LifoQueue()
        l_q = LifoQueue()
        start_cell.isvisited = True
        end_cell.isvisitedl = True
        f_q.put(start_cell)
        l_q.put(end_cell)
        curf = start_cell
        curl = end_cell
        dirs = [[-1, 0], [1, 0], [0, 1], [0, -1]]
        flag = True
        while f_q.qsize() > 0 and l_q.qsize() > 0 and flag:
            curf = f_q.get()
            curl = l_q.get()
            locf = curf.loc
            locl = curl.loc
            if not (curf.isvisitedl or curl.isvisited):
                q.put(curf)
                q.put(curl)
                for dir in dirs:
                    next_xf = locf[1] + dir[1]
                    next_yf = locf[0] + dir[0]
                    if self.can_move(maze, next_xf, next_yf, end_cell):
                        nextf = maze[next_yf][next_xf]
                        if nextf.isvisitedl:
                            curl = nextf
                            flag = False
                            break
                        if not nextf.isvisited:
                            nextf.pre = curf
                            nextf.isvisited = True
                            f_q.put(nextf)
                    next_xl = locl[1] + dir[1]
                    next_yl = locl[0] + dir[0]
                    if self.can_move(maze, next_xl, next_yl, start_cell):
                        nextl = maze[next_yl][next_xl]
                        if nextl.isvisited:
                            curf = nextl
                            flag = False
                            break
                        if not nextl.isvisitedl:
                            nextl.pre = curl
                            nextl.isvisitedl = True
                            l_q.put(nextl)
        if p.qsize() == 0:
            self.split_quene(q.qsize(), p)
        while curf.pre is not None:
            alist.append(curf)
            curf = curf.pre
        alist.append(curf)
        alist.reverse()
        while curl.pre is not None:
            alist.append(curl)
            curl = curl.pre
        alist.append(curl)
        return alist

    def bfs_move(self, maze, start_cell, end_cell, q, p, alist):
        bfs_q = Queue()
        bfs_q.put(start_cell)
        dirs = [[-1, 0], [1, 0], [0, 1], [0, -1]]
        while bfs_q.qsize() > 0 and end_cell.pre is None:
            cur = bfs_q.get()
            q.put(cur)
            loc = cur.loc
            for dir in dirs:
                next_x = loc[1] + dir[1]
                next_y = loc[0] + dir[0]
                if self.can_move(maze, next_x, next_y, end_cell):
                    next = maze[next_y][next_x]
                    if next.isvisited:
                        continue
                    next.pre = cur
                    next.isvisited = True
                    bfs_q.put(next)
        if p.qsize() == 0:
            self.split_quene(q.qsize(), p)
        while end_cell.pre is not None:
            alist.append(end_cell)
            end_cell = end_cell.pre
        alist.append(end_cell)
        alist.reverse()
        return alist

    def double_dfs(self, maze, start_cell, end_cell, q, p, alist):
        f_q = Queue()
        l_q = Queue()
        start_cell.isvisited = True
        end_cell.isvisitedl = True
        f_q.put(start_cell)
        l_q.put(end_cell)
        curf = start_cell
        curl = end_cell
        dirs = [[-1, 0], [1, 0], [0, 1], [0, -1]]
        flag = True
        while f_q.qsize() > 0 and l_q.qsize() > 0 and flag:
            curf = f_q.get()
            curl = l_q.get()
            locf = curf.loc
            locl = curl.loc
            if not (curf.isvisitedl or curl.isvisited):
                q.put(curf)
                q.put(curl)
                for dir in dirs:
                    next_xf = locf[1] + dir[1]
                    next_yf = locf[0] + dir[0]
                    if self.can_move(maze, next_xf, next_yf, end_cell):
                        nextf = maze[next_yf][next_xf]
                        if nextf.isvisitedl:
                            curl = nextf
                            flag = False
                            break
                        if not nextf.isvisited:
                            nextf.pre = curf
                            nextf.isvisited = True
                            f_q.put(nextf)
                    next_xl = locl[1] + dir[1]
                    next_yl = locl[0] + dir[0]
                    if self.can_move(maze, next_xl, next_yl, start_cell):
                        nextl = maze[next_yl][next_xl]
                        if nextl.isvisited:
                            curf = nextl
                            flag = False
                            break
                        if not nextl.isvisitedl:
                            nextl.pre = curl
                            nextl.isvisitedl = True
                            l_q.put(nextl)
        if p.qsize() == 0:
            self.split_quene(q.qsize(), p)
        while curf.pre is not None:
            alist.append(curf)
            curf = curf.pre
        alist.append(curf)
        alist.reverse()
        while curl.pre is not None:
            alist.append(curl)
            curl = curl.pre
        alist.append(curl)
        return alist

    def can_move(self, maze, x, y, end_cell):
        if end_cell.pre is not None:
            return False
        if 0 < x < len(maze[0]) and 0 < y < len(maze):
            if maze[y][x].type == 1:
                return False
            return True
        if x == 0 and y == 1:
            return True
        return False

    def split_quene(self, num, p):
        cur = 1
        sum = 0
        while sum < num // 2:
            p.put(cur)
            cur += 1
            sum += cur
        cur -= 1
        while sum < num - cur and cur > 2:
            p.put(cur)
            cur -= 1
            sum += cur

        return p

    def dispatch_click(self, pos):
        for button in self.BUTTONS:
            x, y, length, height = button['x'], button['y'], button['length'], button['height']
            pos_x, pos_y = pos
            if x <= pos_x <= x + length and y <= pos_y <= y + height:
                return button['click']

    def refresh(self):
        size = mazeMap.random_maze_size()
        Tmaze = generate_maze(size, size)
        return Tmaze

    def draw_maze(self, maze, cur_pos):
        self.SCREEN.fill(self.white)
        self.draw_button(2, 2, self.black, self.WIDTH // 3 - 4, self.HEADER - 4, '刷新地图')
        self.draw_button(self.WIDTH / 3 + 2, 2, self.black, self.WIDTH // 3 - 4, self.HEADER - 4, '广度优先')
        self.draw_button(self.WIDTH / 3 + self.WIDTH / 3 + 2, 2, self.black, self.WIDTH // 3 - 4, self.HEADER - 4,
                         '双向广度优先')
        self.draw_button(2, self.HEADER + 2, self.black, self.WIDTH // 3 - 4, self.HEADER - 4, '双向深度优先')
        self.draw_button(self.WIDTH / 3 + 2, self.HEADER + 2, self.black, self.WIDTH // 3 - 4, self.HEADER - 4,
                         'A-Star')
        self.draw_button(self.WIDTH / 3 * 2 + 2, self.HEADER + 2, self.black, self.WIDTH // 3 - 4, self.HEADER - 4,
                         '双向A-Star')

        if len(self.BUTTONS) == 0:
            self.BUTTONS.extend([{
                "x": 2, "y": 2, "length": self.WIDTH // 3 - 4, 'height': self.HEADER - 4, 'click': 'refresh'
            }, {
                "x": self.WIDTH / 3 + 2, 'y': 2, "length": self.WIDTH // 3 - 4, 'height': self.HEADER - 4,
                'click': 'bfs'
            }, {
                "x": self.WIDTH / 3 + self.WIDTH / 3 + 2, 'y': 2, "length": self.WIDTH // 3 - 4,
                'height': self.HEADER - 4, 'click': 'db_bfs'
            }, {
                "x": 2, "y": self.HEADER + 2, "length": self.WIDTH // 3 - 4, 'height': self.HEADER - 4,
                'click': 'dfs'
            }, {
                "x": self.WIDTH / 3 + 2, "y": self.HEADER + 2, "length": self.WIDTH // 3 - 4, 'height': self.HEADER - 4,
                'click': 'a_star'
            }, {
                "x": self.WIDTH / 3 * 2 + 2, "y": self.HEADER + 2, "length": self.WIDTH // 3 - 4,
                'height': self.HEADER - 4,
                'click': 'db_astar'
            }, ])

        size = len(maze)
        cell_size = int(self.WIDTH / size)
        cell_padding = (self.WIDTH - (cell_size * size)) / 2
        for y in range(size):
            for x in range(size):
                cell = maze[y][x]
                color = self.black if cell.type == 1 else self.red if cell.type == 3 else self.cyan if cell.type == 2 else self.white
                if x == cur_pos.loc[1] and y == cur_pos.loc[0]:
                    color = self.green
                self.draw_rect(cell_padding + x * cell_size, self.HEADER * 2 + cell_padding + y * cell_size,
                               cell_size - 1,
                               color)
        pygame.display.flip()

    def random_maze_size(self):
        return randint(self.min, self.max) * 4 + 1

    def main(self, maze, cur_pos, start_cell, end_cell):
        end_cell = end_cell
        q = Queue(maxsize=0)
        p = Queue(maxsize=0)
        self.draw_maze(maze, cur_pos)
        dirs = [[-1, 0], [1, 0], [0, 1], [0, -1]]
        ai_flag = False
        way_list = []
        while True:
            # pygame.time.Clock().tick(self.FPS)
            for event in pygame.event.get():
                if event.type == pygame.QUIT:
                    exit(0)
                elif event.type == pygame.VIDEORESIZE:
                    size = event.w, event.h
                    self.SCREEN = pygame.display.set_mode(size, pygame.RESIZABLE)
                elif event.type == pygame.MOUSEBUTTONDOWN:
                    mouse_pos = pygame.mouse.get_pos()
                    click = self.dispatch_click(mouse_pos)
                    if click == 'refresh':
                        Tmaze = self.refresh()
                        maze = Tmaze[0]
                        start = Tmaze[1]
                        end = Tmaze[2]
                        start_cell = maze[start[0]][start[1]]
                        cur_pos = maze[start[0]][start[1]]
                        end_cell = maze[end[0]][end[1]]
                        self.draw_maze(maze, start_cell)
                        ai_flag = False
                    if click == 'bfs':
                        ai_flag = True
                        t = Thread(target=self.bfs_move, args=(maze, start_cell, end_cell, q, p, way_list))
                        t.start()
                    if click == 'db_bfs':
                        ai_flag = True
                        t = Thread(target=self.double_dfs, args=(maze, start_cell, end_cell, q, p, way_list))
                        t.start()
                    if click == 'dfs':
                        ai_flag = True
                        t = Thread(target=self.dfs_move, args=(maze, start_cell, end_cell, q, p, way_list))
                        t.start()
                    if click == 'a_star':
                        ai_flag = True
                        t = Thread(target=self.a_star, args=(maze, start_cell, end_cell, q, p, way_list))
                        t.start()
                    if click == 'db_astar':
                        ai_flag = True
                        t = Thread(target=self.db_astar, args=(maze, start_cell, end_cell, q, p, way_list))
                        t.start()
            if ai_flag:
                if q.qsize() > 0:
                    if p.qsize() > 0:
                        cur = q.get()
                        cur.type = 3
                        num = p.get()
                        for i in range(num - 1):
                            cur = q.get()
                            cur.type = 3
                        self.draw_maze(maze, cur)
                    else:
                        cur = q.get()
                        cur.type = 3
                        self.draw_maze(maze, cur)
                elif len(way_list) > 0:
                    cur = way_list.pop(0)
                    cur.type = 2
                    self.draw_maze(maze, cur)

            keys = pygame.key.get_pressed()

            if keys[pygame.K_LEFT]:
                cur_pos = self.move(maze, cur_pos, end_cell, dirs[3])
            if keys[pygame.K_RIGHT]:
                cur_pos = self.move(maze, cur_pos, end_cell, dirs[2])
            if keys[pygame.K_DOWN]:
                cur_pos = self.move(maze, cur_pos, end_cell, dirs[1])
            if keys[pygame.K_UP]:
                cur_pos = self.move(maze, cur_pos, end_cell, dirs[0])


if __name__ == '__main__':
    mazeMap = GameMaze(minsize=2, maxsize=2)
    mazeMap.start_game()
    size = mazeMap.random_maze_size()
    Tmaze = generate_maze(size, size)
    start = Tmaze[1]
    end = Tmaze[2]
    start_cell = Tmaze[0][start[0]][start[1]]
    end_cell = Tmaze[0][end[0]][end[1]]
    end_cell.is_end = True
    mazeMap.main(Tmaze[0], start_cell, start_cell, end_cell)
